package fun.coding.jeffreys.judge;

public class FindKthSmallestInTwoSortedArray {

	public static void main(String[] args) {
		FindKthSmallestInTwoSortedArray ins = new FindKthSmallestInTwoSortedArray();
		int[] a1 = {1, 3, 5};
		int[] b1 = {2, 6};
		System.out.println(ins.findKthSmallestInTwoSortedArray(a1, b1, 4));

		// what if there are dups? like k = 4 in the below case
		int[] a2 = {10, 30, 40, 50, 60};
		int[] b2 = {30, 50, 100,110, 200};
		System.out.println(ins.findKthSmallestInTwoSortedArray(a2, b2, 2));
		
		int[] a3 = {2};
		int[] b3 = {1, 3, 5, 7};
		System.out.println(ins.findKthSmallestInTwoSortedArray(a3, b3, 4));
		
		int[] a4 = {1};
		int[] b4 = {2, 3, 5, 7};
		System.out.println(ins.findKthSmallestInTwoSortedArray(a4, b4, 4));
		
	}


	public int findKthSmallestInTwoSortedArray(int[] a, int[] b, int k) {
		//return helper(a, b, 0, a.length - 1, 0, b.length - 1, k);
		return findKth(a, 0, b, 0, k);
	}

	// This is what I copied from internet
	public int findKth(int[] A, int A_start, int[] B, int B_start, int k){		
		if(A_start >= A.length) 
			return B[B_start + k - 1];
		if(B_start >= B.length)
			return A[A_start + k - 1];

		if (k == 1)
			return Math.min(A[A_start], B[B_start]);

		int A_key = A_start + k / 2 - 1 < A.length ? A[A_start + k / 2 - 1] : Integer.MAX_VALUE;
		int B_key = B_start + k / 2 - 1 < B.length ? B[B_start + k / 2 - 1] : Integer.MAX_VALUE; 

		if (A_key < B_key) {
			return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
		} else {
			return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
		}
	}

	// Not working...
	private int helper(int[] a, int[] b, int aStart, int aEnd, int bStart, int bEnd, int k) {
		if (aEnd - aStart > bEnd - bStart) {
			return helper(b, a, bStart, bEnd, aStart, aEnd, k);
		}

		if (aEnd - aStart + 1 == 0 && bStart - bEnd + 1> 0) {
			return b[k - 1];
		}

		if (k == 1) {
			return Math.min(a[aStart], b[bStart]);
		}

		int i = Math.min(aEnd - aStart + 1, aStart + k/2);
		int j = Math.min(bEnd - bStart + 1, bStart + k/2);

		if (a[i-1] > b[j-1]) {
			return helper(a, b, aStart, aEnd - i, bStart + j, bEnd, k - j);
		} else {
			return helper(a, b, aStart + i, aEnd, bStart, bEnd - j, k/2);
		}
	}


}
